package com.example.code2022;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: dangwen
 * @createDate: 2022/4/25
 * 318. 最大单词长度乘积
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 */
public class P318 {
    public static void main(String[] args) {

    }
    // 1.暴力破解
    public static int solution1(String[] strings){
        int result = 0;
        int length = strings.length;
        for (int i = 0; i < length; i++) {
            String word1 = strings[i];
            for (int j = i + 1; j < length; j++) {
                String word2 = strings[j];
                if (!hasSameWord(word1, word2)){
                    result = Math.max(result, word1.length() * word2.length());
                }
            }
        }
        return result;
    }

    // 2.优化查询逻辑 预查询+位运算
    public static int solution2(String[] strings){
        int result = 0;
        int length = strings.length;
        int[] masks = new int[length];
        for (int i = 0; i < length; i++) {
            String string = strings[i];
            int mask = 0;
            for (int j = 0; j < string.length(); j++) {
                mask |= 1 << (string.charAt(i) - 'a');
            }
            masks[i] = mask;
        }

        for (int i = 0; i < length; i++) {
            String word1 = strings[i];
            for (int j = i + 1; j < length; j++) {
                String word2 = strings[j];
                if ((masks[i] & masks[j]) == 0){
                    result = Math.max(result, word1.length() * word2.length());
                }
            }
        }
        return result;
    }

    // 3.优化查询逻辑 预查询+位运算 + 减少比较次数
    public static int solution(String[] strings){
        int result = 0;
        int length = strings.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            String string = strings[i];
            int mask = 0;
            for (int j = 0; j < string.length(); j++) {
                mask |= 1 << (string.charAt(i) - 'a');
            }
            map.put(mask, Math.max(map.getOrDefault(mask, 0), string.length()));
        }

        for (Integer x : map.keySet()) {
            for (Integer y : map.keySet()) {
                if ((x & y) == 0){
                    result = Math.max(result, map.get(x) * map.get(y));
                }
            }
        }
        return result;
    }

    // n^2
    private static boolean hasSameWord1(String word1, String word2) {
        for (int i = 0; i < word1.length(); i++) {
            if (word1.indexOf(word1.charAt(i)) != 0){
                return true;
            }
        }
        return false;
    }

    // n + 26个空间
    private static boolean hasSameWord2(String word1, String word2) {
        int[] arr = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            char c = word1.charAt(i);
            arr[c - 'a'] = 1;
        }
        for (int i = 0; i < word2.length(); i++){
            char c = word1.charAt(i);
            if (arr[c - 'a'] != 0){
                return true;
            }
        }
        return false;
    }

    // n + 2个空间
    private static boolean hasSameWord(String word1, String word2) {
        int bitMask1 = 0;
        int bitMask2 = 0;
        // 使用bit位作为计算，总共26个bit就能放下所有元素
        for (Character c : word1.toCharArray()) {
            // c应该放在位图的位置：左移 c - 'a'次，元素添加到bitmask上的方式通过或运算
            bitMask1 |= 1 << (c - 'a');
        }
        for (Character c : word2.toCharArray()) {
            bitMask2 |= 1 << (c - 'a');
        }
        return (bitMask1 & bitMask2) != 0;
    }

}
